package com.leetcode.LC;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class LC1030 {
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {

        //利用Map存储坐标和距离，取出距离单独存储排序，然后取值
        //新思路，用TreeMap存储信息，距离和坐标，然后直接取值
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                int dis = Math.abs(i - r0) + Math.abs(j - c0);
                if (map.containsKey(dis)) {
                    List<int[]> list = map.get(dis);
                    list.add(new int[]{i, j});
                    map.put(dis, list);
                } else {
                    List<int[]> list = new ArrayList<>();
                    list.add(new int[]{i, j});
                    map.put(dis, list);
                }
            }
        }
        int[][] ints1 = new int[R * C][2];
        int a = -1;
        for (List<int[]> value : map.values()) {
            for (int[] ints : value) {
                a++;
                ints1[a] = ints;
            }
        }
        return ints1;
    }

    public static void main(String[] args) {
        for (int[] ints : new LC1030().allCellsDistOrder(1, 2, 0, 0)) {
            for (int anInt : ints) {
                System.out.print(anInt + ",");
            }
            System.out.println();
        }
    }
}
